// 删除有序数组中的重复项
// 思路：
// 1. 定义快慢指针，slow走在后面，fast走在前面探路
// 2. fast找到一个不重复的元素就赋值给slow，并且slow++
// PS：赋值和slow++的先后顺序需要注意，请画图理解这部分

class Solution {
public:
    int removeDuplicates(vector<int>& nums) 
    {
        // 定义快慢指针，slow走在后面，fast走在前面探路
        // fast找到不重复的元素就赋值给slow，并且slow++
        // 需要注意赋值和slow++的先后顺序，需要画图去理解
        int slow = 0, fast = 0;

        while(fast < nums.size())
        {
            if(nums[slow] != nums[fast])
            {
                slow++; // slow++在先，后赋值
                nums[slow] = nums[fast];
            }

            fast++;
        }

        // 光看没用，请画图理解
        return slow + 1;
    }
};


// 删除排序链表中的重复元素
class Solution {
public:
    ListNode* deleteDuplicates(ListNode* head) 
    {
        if(head == nullptr)
            return nullptr;

        // 定义快慢指针
        ListNode* slow = head, *fast = head;

        while(fast != nullptr)
        {
            if(slow->val != fast->val)
            {
                slow->next = fast;
                slow = slow->next;
            }

            fast = fast->next;
        }

        // 注意需要断开与后面重复元素的连接
        slow->next = nullptr;

        return head;
    }
};


// 移除元素
class Solution {
public:
    int removeElement(vector<int>& nums, int val) 
    {
        // 定义快慢指针
        // 如果fast遇到值不为val的元素则赋值给slow，并且slow++
        // 还是需要注意赋值和slow++的先后顺序，请画图理解
        int slow = 0, fast = 0;

        while(fast < nums.size())
        {
            if(nums[fast] != val)
            {
                nums[slow] = nums[fast];
                slow++;
            }
            fast++;
        }

        return slow;
    }
};


// 移动零
class Solution {
public:
    void moveZeroes(vector<int>& nums) 
    {
        // 根据 移除元素 思路，将0全部移除
        // 然后再将[p, nums.size()-1]全部置为0即可
        int p = removeElement(nums, 0);

        for(int i = p; i < nums.size(); i++)
        {
            nums[i] = 0;
        }
    }

    // 移除元素
    int removeElement(vector<int>& nums, int val)
    {
        int slow = 0, fast = 0;

        while(fast < nums.size())
        {
            if(nums[fast] != val)
            {
                nums[slow] = nums[fast];
                slow++;
            }
            fast++;
        }

        return slow;
    }
};



